{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Reverse Nodes in Even Length Groups"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #linked-list"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #链表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: reverseEvenLengthGroups"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #反转偶数长度组的节点"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个链表的头节点 <code>head</code> 。</p>\n",
    "\n",
    "<p>链表中的节点 <strong>按顺序</strong> 划分成若干 <strong>非空</strong> 组，这些非空组的长度构成一个自然数序列（<code>1, 2, 3, 4, ...</code>）。一个组的 <strong>长度</strong> 就是组中分配到的节点数目。换句话说：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>节点 <code>1</code> 分配给第一组</li>\n",
    "\t<li>节点 <code>2</code> 和 <code>3</code> 分配给第二组</li>\n",
    "\t<li>节点 <code>4</code>、<code>5</code> 和 <code>6</code> 分配给第三组，以此类推</li>\n",
    "</ul>\n",
    "\n",
    "<p>注意，最后一组的长度可能小于或者等于 <code>1 + 倒数第二组的长度</code> 。</p>\n",
    "\n",
    "<p><strong>反转</strong> 每个 <strong>偶数</strong> 长度组中的节点，并返回修改后链表的头节点 <code>head</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/10/25/eg1.png\" style=\"width: 699px; height: 124px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [5,2,6,3,9,1,7,3,8,4]\n",
    "<strong>输出：</strong>[5,6,2,3,9,1,4,8,3,7]\n",
    "<strong>解释：</strong>\n",
    "- 第一组长度为 1 ，奇数，没有发生反转。\n",
    "- 第二组长度为 2 ，偶数，节点反转。\n",
    "- 第三组长度为 3 ，奇数，没有发生反转。\n",
    "- 最后一组长度为 4 ，偶数，节点反转。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/10/25/eg2.png\" style=\"width: 284px; height: 114px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [1,1,0,6]\n",
    "<strong>输出：</strong>[1,0,1,6]\n",
    "<strong>解释：</strong>\n",
    "- 第一组长度为 1 ，没有发生反转。\n",
    "- 第二组长度为 2 ，节点反转。\n",
    "- 最后一组长度为 1 ，没有发生反转。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/10/28/eg3.png\" style=\"width: 139px; height: 114px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [2,1]\n",
    "<strong>输出：</strong>[2,1]\n",
    "<strong>解释：</strong>\n",
    "- 第一组长度为 1 ，没有发生反转。\n",
    "- 最后一组长度为 1 ，没有发生反转。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>链表中节点数目范围是 <code>[1, 10<sup>5</sup>]</code></li>\n",
    "\t<li><code>0 &lt;= Node.val &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [reverse-nodes-in-even-length-groups](https://leetcode.cn/problems/reverse-nodes-in-even-length-groups/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [reverse-nodes-in-even-length-groups](https://leetcode.cn/problems/reverse-nodes-in-even-length-groups/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[5,2,6,3,9,1,7,3,8,4]', '[1,1,0,6]', '[1,1,0,6,5]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseEvenLengthGroups(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "      if not head or not head.next:\n",
    "        return head\n",
    "      \n",
    "      def reverse(head, tail):\n",
    "        if tail is None:\n",
    "          start = head.next\n",
    "          prev = None\n",
    "\n",
    "          while start:\n",
    "            nxt = start.next\n",
    "            start.next = prev\n",
    "            prev = start\n",
    "            start = nxt\n",
    "\n",
    "          head.next = prev\n",
    "\n",
    "          return None\n",
    "        else:\n",
    "          start = head.next\n",
    "          end = start\n",
    "          prev = None\n",
    "\n",
    "          while start is not tail:\n",
    "            nxt = start.next\n",
    "            start.next = prev\n",
    "            prev = start\n",
    "            start = nxt\n",
    "          \n",
    "          head.next = prev\n",
    "          end.next = tail\n",
    "\n",
    "          return end\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "      dummy = ListNode()\n",
    "      dummy.next = head\n",
    "      h = dummy\n",
    "      cnt = 1\n",
    "      while True:\n",
    "        k = 0\n",
    "\n",
    "        headNode = h\n",
    "        while k < cnt and h.next:\n",
    "          h = h.next\n",
    "          k += 1\n",
    "\n",
    "        tailNode = h.next # None/node\n",
    "\n",
    "        if k % 2 == 0:\n",
    "          back = reverse(headNode, tailNode)\n",
    "        \n",
    "        if tailNode is None:\n",
    "          break\n",
    "\n",
    "        if k % 2 == 0:\n",
    "            h = back\n",
    "    \n",
    "\n",
    "        cnt += 1\n",
    "      \n",
    "      return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseEvenLengthGroups(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        i = 0  # 统计组数，组数=每组节点数上限，第1组有1个节点，第i组最多有i个节点\n",
    "\n",
    "        dummyhead = ListNode(0, next=head)\n",
    "        \n",
    "        # 初始化当前组的 前驱节点 和 首节点\n",
    "        prev, curr = dummyhead, head\n",
    "\n",
    "        while curr:\n",
    "            i += 1\n",
    "            ptr = curr  # 临时指针\n",
    "            \n",
    "            # 获取当前组的节点数length\n",
    "            length = 0\n",
    "            while length < i and ptr:\n",
    "                length += 1\n",
    "                ptr = ptr.next\n",
    "            \n",
    "            # 若当前组的长度为奇数，不用反转\n",
    "            if length % 2:\n",
    "                for _ in range(length):\n",
    "                    prev, curr = curr, curr.next\n",
    "            \n",
    "            # 若当前组的长度为偶数，要反转\n",
    "            else:\n",
    "                # after iteration, curr is at the end of current group\n",
    "                for _ in range(length-1):\n",
    "                    succ = curr.next \n",
    "                    curr.next = succ.next  \n",
    "                    succ.next = prev.next \n",
    "                    prev.next = succ\n",
    "\n",
    "                prev, curr = curr, curr.next \n",
    "\n",
    "        return dummyhead.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseEvenLengthGroups(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        def reverse(head, tail):\n",
    "            pre = tail.next\n",
    "            cur = head\n",
    "            while pre!=tail:\n",
    "                nxt = cur.next\n",
    "                cur.next = pre\n",
    "                pre = cur\n",
    "                cur = nxt\n",
    "            return tail, head\n",
    "\n",
    "\n",
    "        dummy = ListNode(-1)\n",
    "        dummy.next = head\n",
    "\n",
    "        pre = dummy\n",
    "        group_id = 1\n",
    "        while head:\n",
    "            for i in range(group_id-1):\n",
    "                pre = head\n",
    "                head = head.next\n",
    "                if not head:\n",
    "                    return dummy.next\n",
    "\n",
    "            tail = head\n",
    "            cnt = 1\n",
    "            for i in range(group_id-1):\n",
    "                if tail.next:\n",
    "                    tail = tail.next\n",
    "                    cnt += 1\n",
    "            if cnt%2 == 0:\n",
    "                next_node = tail.next\n",
    "                h, t = reverse(head, tail)\n",
    "                \n",
    "                pre.next = h\n",
    "                t.next = next_node\n",
    "                \n",
    "                head = h\n",
    "\n",
    "            group_id += 1\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseEvenLengthGroups(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        ans_head, n, i, cur = ListNode(), 1, 0, head\n",
    "        cur2 = ans_head\n",
    "        while cur:\n",
    "            i += 1\n",
    "            cur = cur.next\n",
    "            if i == n and n % 2:\n",
    "                while head != cur:\n",
    "                    cur2.next, head = head, head.next\n",
    "                    cur2 = cur2.next\n",
    "                n, i = n+1, 0\n",
    "            elif (cur is None and i % 2 == 0) or (i == n and n % 2 == 0):\n",
    "                start = head\n",
    "                while head != cur:\n",
    "                    node, head = head, head.next\n",
    "                    node.next, cur2.next = cur2.next, node\n",
    "                cur2 = start\n",
    "                cur2.next = cur\n",
    "                n, i = n+1, 0\n",
    "\n",
    "        return ans_head.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseEvenLengthGroups(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "      if not head or not head.next:\n",
    "        return head\n",
    "      \n",
    "      def reverse(head, tail):\n",
    "        if tail is None:\n",
    "          start = head.next\n",
    "          prev = None\n",
    "\n",
    "          while start:\n",
    "            nxt = start.next\n",
    "            start.next = prev\n",
    "            prev = start\n",
    "            start = nxt\n",
    "\n",
    "          head.next = prev\n",
    "\n",
    "          return None\n",
    "        else:\n",
    "          start = head.next\n",
    "          end = start\n",
    "          prev = None\n",
    "\n",
    "          while start is not tail:\n",
    "            nxt = start.next\n",
    "            start.next = prev\n",
    "            prev = start\n",
    "            start = nxt\n",
    "          \n",
    "          head.next = prev\n",
    "          end.next = tail\n",
    "\n",
    "          return end\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "      dummy = ListNode()\n",
    "      dummy.next = head\n",
    "      h = dummy\n",
    "      cnt = 1\n",
    "      while True:\n",
    "        k = 0\n",
    "\n",
    "        headNode = h\n",
    "        while k < cnt and h.next:\n",
    "          h = h.next\n",
    "          k += 1\n",
    "\n",
    "        tailNode = h.next # None/node\n",
    "\n",
    "        if k % 2 == 0:\n",
    "          back = reverse(headNode, tailNode)\n",
    "        \n",
    "        if tailNode is None:\n",
    "          break\n",
    "\n",
    "        if k % 2 == 0:\n",
    "          if back is None:\n",
    "            break\n",
    "          else:\n",
    "            h = back\n",
    "    \n",
    "\n",
    "        cnt += 1\n",
    "      \n",
    "      return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def reverseEvenLengthGroups(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        ans = head\n",
    "        nnode, pre = 1, None\n",
    "        while head:\n",
    "            n, dummy, tail = 0, head, head\n",
    "            while head and n < nnode:\n",
    "                n += 1\n",
    "                tail = head\n",
    "                head = head.next\n",
    "            if n & 1 == 0:\n",
    "                p, cur = head, dummy\n",
    "                while cur != head:\n",
    "                    next = cur.next\n",
    "                    cur.next = p\n",
    "                    p = cur\n",
    "                    cur = next\n",
    "                if pre:\n",
    "                    pre.next = tail\n",
    "            pre = dummy if n & 1 == 0 else tail\n",
    "            nnode += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseEvenLengthGroups(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        def reverse(start, end):\n",
    "            p = start.next\n",
    "            end = slow = end.next\n",
    "            while p != end:\n",
    "                temp = p.next\n",
    "                p.next = slow\n",
    "                slow = p\n",
    "                p = temp\n",
    "            start.next = slow\n",
    "        count = 0\n",
    "        p = head\n",
    "        while p.next:\n",
    "            count += 1\n",
    "            num = count+1\n",
    "            start = p\n",
    "            while num and p.next:\n",
    "                p = p.next\n",
    "                num -= 1\n",
    "            \n",
    "            if (num % 2 == 0 and count % 2 == 1) or (count % 2 == 0 and num % 2 == 1):\n",
    "                temp = start.next\n",
    "                reverse(start, p)\n",
    "                p = temp\n",
    "            if num > 0:\n",
    "                break\n",
    "        return head\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseEvenLengthGroups(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        def rev(h, k):\n",
    "            t = h.next\n",
    "            for i in range(k-1):\n",
    "                if t.next is None:\n",
    "                    return t\n",
    "                tar = t.next\n",
    "                t.next = tar.next\n",
    "                tar.next = h.next\n",
    "                h.next = tar\n",
    "            return t\n",
    "        def forward(h, k):\n",
    "            n = 0\n",
    "            for i in range(k):\n",
    "                if h.next is None:\n",
    "                    return h, n\n",
    "                h = h.next\n",
    "                n += 1\n",
    "            return h, n\n",
    "        r = head\n",
    "        i = 2\n",
    "        while r.next is not None:\n",
    "            temp, n = forward(r, i)\n",
    "            if n > 0 and n%2 == 0:\n",
    "                r = rev(r, i)\n",
    "            else:\n",
    "                r = temp\n",
    "            i += 1\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self,head):\n",
    "        new_head=None\n",
    "        while head!=None:\n",
    "            tmp=head.next\n",
    "            head.next=new_head\n",
    "            new_head=head\n",
    "            head=tmp\n",
    "        return new_head\n",
    "    def reverseEvenLengthGroups(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        cnt=2\n",
    "        p=head\n",
    "        while p.next!=None:\n",
    "            tail=p\n",
    "            i=0\n",
    "            for _ in range(cnt):                \n",
    "                if tail.next==None:\n",
    "                    break\n",
    "                tail=tail.next\n",
    "                i+=1\n",
    "            cnt=min(cnt,i)\n",
    "            tmp=tail.next\n",
    "            if cnt%2==0:\n",
    "                tail.next=None\n",
    "                start=p.next\n",
    "                new_head=self.reverseList(start)\n",
    "                p.next=new_head\n",
    "                start.next=tmp\n",
    "                p=start\n",
    "            else:\n",
    "                p=tail\n",
    "            cnt+=1\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseEvenLengthGroups(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        def reverse(start, end):\n",
    "            p = start.next\n",
    "            end = slow = end.next\n",
    "            while p != end:\n",
    "                temp = p.next\n",
    "                p.next = slow\n",
    "                slow = p\n",
    "                p = temp\n",
    "            start.next = slow\n",
    "        count = 0\n",
    "        p = head\n",
    "        while p.next:\n",
    "            count += 1\n",
    "            num = count+1\n",
    "            start = p\n",
    "            while num and p.next:\n",
    "                p = p.next\n",
    "                num -= 1\n",
    "            if (num % 2 == 0 and count % 2) or (count % 2 == 0 and num % 2):\n",
    "                temp = start.next\n",
    "                reverse(start, p)\n",
    "                p = temp\n",
    "            if num > 0:\n",
    "                break\n",
    "        return head\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseEvenLengthGroups(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        def reverse(head, tail):\n",
    "            pre = None\n",
    "            cur = head\n",
    "            while pre!=tail:\n",
    "                nxt = cur.next\n",
    "                cur.next = pre\n",
    "                pre = cur\n",
    "                cur = nxt\n",
    "            return tail, head\n",
    "\n",
    "\n",
    "        dummy = ListNode(-1)\n",
    "        dummy.next = head\n",
    "\n",
    "        pre = dummy\n",
    "        group_id = 1\n",
    "        while head:\n",
    "            for i in range(group_id-1):\n",
    "                pre = head\n",
    "                head = head.next\n",
    "                if not head:\n",
    "                    return dummy.next\n",
    "\n",
    "            tail = head\n",
    "            cnt = 1\n",
    "            for i in range(group_id-1):\n",
    "                if tail.next:\n",
    "                    tail = tail.next\n",
    "                    cnt += 1\n",
    "            if cnt%2 == 0:\n",
    "                next_node = tail.next\n",
    "                h, t = reverse(head, tail)\n",
    "                \n",
    "                pre.next = h\n",
    "                t.next = next_node\n",
    "                \n",
    "                head = h\n",
    "\n",
    "            group_id += 1\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseEvenLengthGroups(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        group, prev, pos, stack = 1, None, head, []\n",
    "        while pos:\n",
    "            this_head = prev\n",
    "            count = 0\n",
    "            while pos and count < group:\n",
    "                stack.append(pos)\n",
    "                prev = pos\n",
    "                pos = pos.next\n",
    "                count += 1\n",
    "\n",
    "            if len(stack) % 2 == 0:\n",
    "                this_pos = this_head\n",
    "                while stack:\n",
    "                    stack[-1].next = None\n",
    "                    this_pos.next = stack.pop()\n",
    "                    this_pos = this_pos.next\n",
    "                prev = this_pos\n",
    "                this_pos.next = pos\n",
    "            else:\n",
    "                stack.clear()\n",
    "            group += 1\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseEvenLengthGroups(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        l = []\n",
    "        node = head\n",
    "        while node:\n",
    "            l.append(node.val)\n",
    "            node = node.next\n",
    "\n",
    "        add = 1\n",
    "        cur = 1\n",
    "        while cur <= len(l):\n",
    "            if add & 1 == 0:\n",
    "                l[cur - add:cur] = l[cur - add:cur][::-1]\n",
    "            add += 1\n",
    "            cur += add\n",
    "        if cur - add - len(l):\n",
    "            rest = len(l) - (cur - add)\n",
    "            if rest & 1 == 0:\n",
    "                l[-rest:] = l[-rest:][::-1]\n",
    "        \n",
    "        node = head\n",
    "        for v in l:\n",
    "            node.val = v\n",
    "            node = node.next\n",
    "        \n",
    "        return head\n",
    "        \n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseEvenLengthGroups(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        i = 0\n",
    "        cur, pre = head, None\n",
    "        while cur:\n",
    "            i += 1\n",
    "            it = cur\n",
    "            length = 0\n",
    "            while length < i and it:\n",
    "                length += 1\n",
    "                it = it.next\n",
    "            \n",
    "            if length & 1:\n",
    "                for j in range(length):\n",
    "                    pre, cur = cur, cur.next\n",
    "            else:\n",
    "                for j in range(length - 1):\n",
    "                    pre.next, cur.next.next, cur.next = cur.next, pre.next, cur.next.next\n",
    "                pre, cur = cur, cur.next\n",
    "\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseEvenLengthGroups(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        evenGroups = []\n",
    "        curr = head\n",
    "\n",
    "        start = 1  # start position of group1\n",
    "        i = 0   # group index\n",
    "        while curr:\n",
    "            i += 1\n",
    "            length = 0\n",
    "            while length < i and curr:\n",
    "                length += 1\n",
    "                curr = curr.next\n",
    "            \n",
    "            if length % 2 == 0:\n",
    "                evenGroups.append((start, start+length-1))\n",
    "            start += length \n",
    "                  \n",
    "        for start, end in evenGroups:\n",
    "            head = self.reverseBetween(head, start, end)\n",
    "        \n",
    "        return head\n",
    "    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:\n",
    "        dummyHead = ListNode(0, next=head)\n",
    "        prev, curr = dummyHead, head\n",
    "\n",
    "        # find start position of reversion\n",
    "        # after iteration, prev is at `left`-1 position, curr is at `left` position\n",
    "        for _ in range(left-1): \n",
    "            prev, curr = prev.next, curr.next            \n",
    "\n",
    "        # reverse linked list in [left, right] \n",
    "        # during iteration, prev is at always at `left`-1 position, succ is always be inserted between prev and node at `left` position, thus becomes at `left` position\n",
    "        # after iteration, curr is at `right` position\n",
    "        for _ in range(left, right):\n",
    "            succ = curr.next \n",
    "            curr.next = succ.next  \n",
    "            succ.next = prev.next \n",
    "            prev.next = succ \n",
    "\n",
    "        return dummyHead.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseEvenLengthGroups(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        i = 0\n",
    "        cur, pre = head, None\n",
    "        while cur:\n",
    "            i += 1\n",
    "            it = cur\n",
    "            length = 0\n",
    "            while length < i and it:\n",
    "                length += 1\n",
    "                it = it.next\n",
    "            \n",
    "            if length & 1:\n",
    "            # if length % 2 != 0:\n",
    "                for j in range(length):\n",
    "                    pre, cur = cur, cur.next\n",
    "            else:\n",
    "                for j in range(length - 1):\n",
    "                    pre.next, cur.next.next, cur.next = cur.next, pre.next, cur.next.next\n",
    "                pre, cur = cur, cur.next\n",
    "\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseEvenLengthGroups(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        i = 0\n",
    "        cur, pre = head, None\n",
    "        while cur:\n",
    "            i += 1\n",
    "            it = cur\n",
    "            length = 0\n",
    "            while length < i and it:\n",
    "                length += 1\n",
    "                it = it.next\n",
    "            if length & 1:\n",
    "                for j in range(length):\n",
    "                    pre, cur = cur, cur.next\n",
    "            else:\n",
    "                for j in range(length - 1):\n",
    "                    pre.next, cur.next.next, cur.next = cur.next, pre.next, cur.next.next\n",
    "                pre, cur = cur, cur.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseEvenLengthGroups(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        group = 1\n",
    "        curr = stop = head\n",
    "        temp = []\n",
    "        while curr:\n",
    "            if len(temp) == group:\n",
    "                if group % 2 == 0:\n",
    "                    temp = temp[::-1]\n",
    "                for node in temp:\n",
    "                    stop.next = node\n",
    "                    stop = node\n",
    "                stop.next = None\n",
    "                temp.clear()\n",
    "                group += 1\n",
    "            temp.append(curr)\n",
    "            curr = curr.next\n",
    "        \n",
    "        if len(temp) > 0:\n",
    "            if len(temp) % 2 == 0:\n",
    "                temp = temp[::-1]\n",
    "            for node in temp:\n",
    "                stop.next = node\n",
    "                stop = node\n",
    "            stop.next = None\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseEvenLengthGroups(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if not head:return None\n",
    "        cnt = 1\n",
    "        p = head\n",
    "        F = []\n",
    "        while p:\n",
    "            c = 0;ed = p\n",
    "            r = []\n",
    "            while c < cnt and ed:\n",
    "                r.append(ed.val)\n",
    "                ed = ed.next\n",
    "                c += 1\n",
    "            F.append(r)\n",
    "            cnt += 1\n",
    "            p = ed\n",
    "        for idx,i in enumerate(F):\n",
    "            if not len(i) % 2:\n",
    "                F[idx] = i[::-1]\n",
    "        L = []\n",
    "        for i in F:\n",
    "            L.extend(i)\n",
    "        p = head;pos = 0\n",
    "        while p:\n",
    "            p.val = L[pos]\n",
    "            p = p.next;pos += 1\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseEvenLengthGroups(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        def reverse(l):\n",
    "            temp=l\n",
    "            curr=None\n",
    "            while temp:\n",
    "                ss=temp.next \n",
    "                temp.next=curr \n",
    "                curr=temp \n",
    "                temp=ss  \n",
    "            return curr\n",
    "        jishu=[]\n",
    "        oushu=[]\n",
    "        n=1\n",
    "        while head:\n",
    "            temp=n+1\n",
    "            if n%2==1:\n",
    "                temp1=ListNode(-1)\n",
    "                temp2=temp1 \n",
    "                temp2.next=head  \n",
    "                while head and n>0:\n",
    "                    head=head.next\n",
    "                    temp2=temp2.next\n",
    "                    n-=1\n",
    "                temp2.next=None \n",
    "                if (temp-1-n)%2==1:\n",
    "                    jishu.append(temp1.next)\n",
    "                else:\n",
    "                    oushu.append(temp1.next)\n",
    "            elif n%2==0:\n",
    "                temp1=ListNode(-1)\n",
    "                temp2=temp1 \n",
    "                temp2.next=head\n",
    "                while head and n>0: \n",
    "                    head=head.next\n",
    "                    temp2=temp2.next\n",
    "                    n-=1\n",
    "                temp2.next=None \n",
    "                if (temp-1-n)%2==1:\n",
    "                    jishu.append(temp1.next)\n",
    "                else:\n",
    "                    oushu.append(temp1.next)\n",
    "            n=temp \n",
    "        for l in range(len(oushu)):\n",
    "            oushu[l]=reverse(oushu[l])\n",
    "        res=ListNode(-1)\n",
    "        dummy=res\n",
    "        i=0 \n",
    "        while i<max(len(jishu),len(oushu)):\n",
    "            if i<len(jishu):\n",
    "                dummy.next=jishu[i]\n",
    "                while jishu[i]:\n",
    "                    dummy=dummy.next \n",
    "                    jishu[i]=jishu[i].next \n",
    "            if i<len(oushu):\n",
    "                dummy.next=oushu[i]\n",
    "                while oushu[i]:\n",
    "                    dummy=dummy.next \n",
    "                    oushu[i]=oushu[i].next\n",
    "            i+=1\n",
    "        return res.next \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "class ListNode:\n",
    "    def __init__(self, val=0, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "class Solution:\n",
    "    def reverseEvenLengthGroups(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        start = 1\n",
    "        cur = head\n",
    "        data = defaultdict(list)\n",
    "        while cur:\n",
    "            for _ in range(start):\n",
    "                data[start].append(cur.val)\n",
    "                cur = cur.next\n",
    "                if not cur:\n",
    "                    break\n",
    "            start += 1\n",
    "        start = 1\n",
    "        cur = head\n",
    "        while cur:\n",
    "            n = len(data[start])\n",
    "            for _ in range(start):\n",
    "                if n % 2 == 0:\n",
    "                    cur.val = data[start].pop()\n",
    "                cur = cur.next\n",
    "                if not cur:\n",
    "                    break\n",
    "            start += 1\n",
    "        return head\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseEvenLengthGroups(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        dummy = ListNode(val = -1, next = head)\n",
    "        pre, srt = dummy, dummy.next\n",
    "        i = 1\n",
    "        while srt:\n",
    "            # 找到头，尾和需要翻转的链表长度\n",
    "            N = 0\n",
    "            for _ in range(i):\n",
    "                if srt:\n",
    "                    srt = srt.next\n",
    "                    N+=1\n",
    "                else:\n",
    "                    break\n",
    "            nxt = srt # 下一轮第一个待处理的节点\n",
    "            srt = pre.next\n",
    "            if not N%2:\n",
    "                pre.next = self.reverseN(srt, N)\n",
    "                srt.next = nxt\n",
    "                pre = srt\n",
    "                srt = nxt\n",
    "            else:\n",
    "                for _ in range(N):\n",
    "                    pre = pre.next\n",
    "                srt = nxt\n",
    "            i+=1\n",
    "        return dummy.next\n",
    "\n",
    "\n",
    "    # 翻转以srt为开头,长度为N的链表\n",
    "    def reverseN(self, node, N):\n",
    "        if N == 1:\n",
    "            return node\n",
    "        else:\n",
    "            last = self.reverseN(node.next, N-1)\n",
    "            node.next.next = node\n",
    "            return last"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverse(self,head,end):\n",
    "        if head.next == end:\n",
    "            return head\n",
    "\n",
    "        \n",
    "        p = head.next\n",
    "        t = self.reverse(p,end)\n",
    "        head.next = None\n",
    "        p.next = head\n",
    "        return t\n",
    "    def reverseEvenLengthGroups(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        self.dfs(head,1)\n",
    "\n",
    "        return head\n",
    "\n",
    "    def dfs(self,head,group):\n",
    "        if not head:\n",
    "            return head\n",
    "        head0 = head\n",
    "        pre = None\n",
    "        g = 0\n",
    "        for i in range(group):\n",
    "            if head:\n",
    "                g += 1\n",
    "                pre = head\n",
    "                head = head.next\n",
    "        if g % 2 ==0:\n",
    "            p = self.reverse(head0,head)\n",
    "            head0.next = self.dfs(head,group+1)\n",
    "            return p\n",
    "        \n",
    "        else:\n",
    "            pre.next = self.dfs(head,group+1)\n",
    "            return head0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseEvenLengthGroups(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        self.len=0\n",
    "        p=head\n",
    "        while p:\n",
    "            p=p.next\n",
    "            self.len+=1\n",
    "        def dfs(T,num):\n",
    "            if num>self.len:\n",
    "                num=self.len\n",
    "            if not T:\n",
    "                return T\n",
    "            if num%2==1:\n",
    "                p=T\n",
    "                i=0\n",
    "                while i<num-1 and p.next:\n",
    "                    p=p.next\n",
    "                    i+=1\n",
    "                if i==num-1:\n",
    "                    self.len-=num\n",
    "                    p.next=dfs(p.next,num+1)\n",
    "                return T\n",
    "            else:\n",
    "                p,q=T,T.next\n",
    "                p.next=None\n",
    "                i=0\n",
    "                while q and i<num-1:\n",
    "                    tmp=q.next\n",
    "                    q.next=p\n",
    "                    p,q=q,tmp\n",
    "                    i+=1\n",
    "                if i==num-1:\n",
    "                    self.len-=num\n",
    "                    T.next=dfs(q,num+1)\n",
    "                    \n",
    "                return p\n",
    "        return dfs(head,1)\n",
    "\n",
    "                    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseEvenLengthGroups(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "\n",
    "        def dfs(head: ListNode, i: int) -> ListNode:\n",
    "            \"\"\"\n",
    "            i: group index, start from 1\n",
    "            \"\"\"     \n",
    "            if not head:\n",
    "                return  \n",
    "            dummyHead = ListNode(0, next=head)\n",
    "            pred, curr = dummyHead, head\n",
    "\n",
    "            # calculate length of linked list\n",
    "            length = 0\n",
    "            while curr and length < i:\n",
    "                pred, curr = pred.next, curr.next\n",
    "                length += 1\n",
    "\n",
    " \n",
    "            if length % 2:  # odd length, no reverse\n",
    "                newHead = head \n",
    "                pred.next = dfs(curr, i+1)\n",
    "                return newHead \n",
    "\n",
    "            else:           # even length, reverse\n",
    "                newHead, nextNode = self.reverseTopN(head, length)\n",
    "                head.next = dfs(nextNode, i+1)\n",
    "                return newHead \n",
    "\n",
    "\n",
    "        return dfs(head, 1) \n",
    "\n",
    "    def reverseTopN(self, head: ListNode, n: int) -> (ListNode, ListNode):\n",
    "        \"\"\"\n",
    "        reverse the top N nodes in the linked list,\n",
    "        return the head of reversed sublist, and the node following the sublist\n",
    "\n",
    "        helper function in Leetcode 92. Reverse Linked List II\n",
    "\n",
    "        T: O(N)\n",
    "        S: O(N)\n",
    "        \"\"\"\n",
    "        if n == 1:\n",
    "            return head, head.next\n",
    "        \n",
    "        newHead, nextNode = self.reverseTopN(head.next, n - 1)\n",
    "        head.next.next = head\n",
    "        head.next = nextNode\n",
    "        \n",
    "        return newHead, nextNode"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseEvenLengthGroups(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        A=[]\n",
    "        x=head\n",
    "        mp=defaultdict(list)\n",
    "        idx={}\n",
    "        p=1\n",
    "        c=1\n",
    "        while x:\n",
    "            A.append(x.val)\n",
    "            mp[p].append(x.val)\n",
    "            idx[c]=p\n",
    "            x=x.next\n",
    "            if len(mp[p])==p:\n",
    "                p+=1\n",
    "            c+=1\n",
    "        x=head\n",
    "        c=1\n",
    "        while x:\n",
    "            if len(mp[idx[c]])&1==0:\n",
    "                k=c-(1+(idx[c]-1))*(idx[c]-1)//2\n",
    "                x.val=mp[idx[c]][-k]\n",
    "            x=x.next\n",
    "            c+=1\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseEvenLengthGroups(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        ans = []\n",
    "        nums = []\n",
    "        d = 1\n",
    "        while head:\n",
    "            nums.append(head.val)\n",
    "            head = head.next\n",
    "            if len(nums) == d:\n",
    "                if d & 1:\n",
    "                    ans.extend(nums[::1])\n",
    "                else:\n",
    "                    ans.extend(nums[::-1])\n",
    "                d += 1\n",
    "                nums = []\n",
    "        if len(nums) & 1:\n",
    "            ans.extend(nums[::1])\n",
    "        else:\n",
    "            ans.extend(nums[::-1])\n",
    "        \n",
    "        dummy = ListNode()\n",
    "        cur = dummy\n",
    "        for x in ans:\n",
    "            cur.next = ListNode(x)\n",
    "            cur = cur.next\n",
    "        return dummy.next\n",
    "                \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseEvenLengthGroups(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        tmp=[]\n",
    "        while head:\n",
    "            tmp.append(head.val)\n",
    "            head=head.next \n",
    "        i,n=0,len(tmp)\n",
    "        cnt=1\n",
    "        while i<n:\n",
    "            s=i\n",
    "            for _ in range(cnt):\n",
    "                i+=1\n",
    "                if i==n:break\n",
    "            cnt+=1\n",
    "            if (i-s)%2==0:\n",
    "                # print(tmp[s:i])\n",
    "                tmp[s:i]=tmp[s:i][::-1]\n",
    "                # print(tmp)\n",
    "        dummy=ListNode(-1)          \n",
    "        cur=dummy\n",
    "        for x in tmp:\n",
    "            cur.next=ListNode(x)      \n",
    "            cur=cur.next \n",
    "        return dummy.next\n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "from typing import Optional\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def reverseEvenLengthGroups(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        def scan(head, paths):\n",
    "            if head is None:\n",
    "                return []\n",
    "            cursor = head\n",
    "            index = 1\n",
    "            while cursor:\n",
    "                arr = []\n",
    "                counter = 0\n",
    "                while cursor and counter<index:\n",
    "                    arr.append(cursor.val)\n",
    "                    cursor = cursor.next\n",
    "                    counter += 1\n",
    "                # 如果是偶数个数直接反转\n",
    "                if arr.__len__() % 2 == 0:\n",
    "                    paths.append(arr[::-1])\n",
    "                else:\n",
    "                    paths.append(arr)\n",
    "                index += 1\n",
    "            # print(\"paths=\", paths)\n",
    "\n",
    "        def rebuild(paths):\n",
    "            if paths.__len__() == 0:\n",
    "                return None\n",
    "            new_head = ListNode(0)\n",
    "            cursor = new_head\n",
    "            for arr in paths:\n",
    "                for val in arr:\n",
    "                    node = ListNode(val)\n",
    "                    cursor.next = node\n",
    "                    cursor = node\n",
    "            return new_head.next\n",
    "\n",
    "        paths = []\n",
    "        scan(head, paths)\n",
    "        return rebuild(paths)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseEvenLengthGroups(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        l, cnt = [], 0\n",
    "        while head:\n",
    "            l.append([])\n",
    "            cnt += 1\n",
    "            for i in range(cnt):\n",
    "                if head:\n",
    "                    l[-1].append(head.val)\n",
    "                    head = head.next\n",
    "        p = head = ListNode(l[0][0])\n",
    "        for x in l[1:]:\n",
    "            if len(x)%2==0: x=x[::-1]\n",
    "            for i in x:\n",
    "                p.next = ListNode(i)\n",
    "                p = p.next\n",
    "        return head    \n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
